#include <string.h>

#include <iostream>
using std::cout;
using std::endl;

void Swap(int& a, int& b) {
  int tmp = a;
  a = b;
  b = tmp;
}
int Partition(int arr[], int first, int last) {
  if (first >= last) return first;
  int splitIdx = first;  // 始终指向已排序部分右区间第一个
  for (int i = first; i < last; ++i) {
    if (arr[i] > arr[last]) {
      Swap(arr[splitIdx], arr[i]);
      splitIdx++;
    }
  }
  Swap(arr[splitIdx], arr[last]);  // 最后指向分区点
  return splitIdx;
}
void RecurQuickFind(int arr[], int first, int last, int bigN) {
  if (first >= last) return;
  int splitIdx = Partition(arr, first, last);
  if (splitIdx + 1 == bigN) {
    return;
  } else if (splitIdx + 1 > bigN) {
    RecurQuickFind(arr, first, splitIdx - 1, bigN);
  } else {
    RecurQuickFind(arr, splitIdx + 1, last, bigN);
  }
}
// 找出无序数组中第N大的数据，要求时间复杂度O(n)。利用快排的思想
int FindNbig(int arr[], int size, int bigN) {
  RecurQuickFind(arr, 0, size - 1, bigN);
  return arr[bigN - 1];
}
void TestFindNbig() {
  int arr[] = {3, 1, 54, 6, 11, 6, 7, 78, 5, 34};
  int n = FindNbig(arr, sizeof(arr) / sizeof(int), 4);
  cout << "FindNbig: " << n << endl;
}

// 桶排序。适用于可以分为n个区间的数据

// 计数排序。适用于：50万考生 0～600分这种排序
void CountSort(int arr[], int size) {
  if (size <= 1) return;
  int min = arr[0], max = arr[0];
  for (int i = 1; i < size; ++i) {
    if (arr[i] > max) max = arr[i];
    if (arr[i] < min) min = arr[i];
  }
  if (min != 0) {
    cout << "min is not 0, not support now\n";
    return;
  }

  int countSize = max + 1;
  int* countArr = new int[countSize];
  memset(countArr, 0, countSize * sizeof(int));
  for (int i = 0; i < size; ++i) {
    countArr[arr[i]] += 1;
  }

  for (int i = 1; i < countSize; ++i) {
    countArr[i] = countArr[i - 1] + countArr[i];
  }

  int* newArr = new int[size];
  for (int i = size - 1; i >= 0; --i) {
    int pos = countArr[arr[i]] - 1;
    newArr[pos] = arr[i];
    countArr[arr[i]]--;
  }

  for (int i = 0; i < size; ++i) {
    arr[i] = newArr[i];
  }

  delete[] countArr;
  delete[] newArr;
}

// 基数排序。适用于几十万手机号码(11位0~9之间的数字)排序，从后往前每一位用计数排序

typedef void (*SortFunc)(int arr[], int size);

void Print(int arr[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}

void TestSort(SortFunc sort) {
  int arr[] = {4, 5, 2, 4, 6, 7, 8, 5, 3, 2, 2, 5, 7, 8, 9,
               9, 0, 0, 1, 2, 3, 6, 4, 5, 9, 8, 7, 6, 0};
  sort(arr, sizeof(arr) / sizeof(int));
  Print(arr, sizeof(arr) / sizeof(int));
}

int main() {
  TestSort(CountSort);
  TestFindNbig();
}